We study a gossip protocol called forwarding without repeating (FWR). Theobjective is to spread multiple rumors over a graph as efficiently as possible.FWR accomplishes this by having nodes record which messages they have forwardedto each neighbor, so that each message is forwarded at most once to eachneighbor. We prove that FWR spreads a rumor over a strongly connected digraph,with high probability, in time which is within a constant factor of optimal fordigraphs with bounded out-degree. Moreover, on digraphs with bounded out-degreeand bounded number of rumors, the number of transmissions required by FWR isarbitrarily better than that of existing approaches. Specifically, FWR requiresO(n) messages on bounded-degree graphs with n nodes, whereas classicalforwarding and an approach based on network coding both require {\omega}(n)messages. Our results are obtained using combinatorial and probabilisticarguments. Notably, they do not depend on expansion properties of theunderlying graph, and consequently the message complexity of FWR is arbitrarilybetter than classical forwarding even on constant-degree expander graphs, as n\rightarrow \infty. In resource-constrained applications, where eachtransmission consumes battery power and bandwidth, our results suggest thatusing a small amount of memory at each node leads to a significant savings.
展开▼
